// 旋转链表

package Leetcode;

class solution_061 {
    /**
     * Definition for singly-linked list.
     * public class ListNode {
     * int val;
     * ListNode next;
     * ListNode() {}
     * ListNode(int val) { this.val = val; }
     * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    class Solution {
        public ListNode rotateRight(ListNode head, int k) {
            int length = 0;
            ListNode pre = head;
            ListNode last = null; // 链表最后一个结点
            // 求链表表长
            while (pre != null) {
                length++;
                last = pre;
                pre = pre.next;
            }
            if (length == 0)
                return null;
            pre = head; // 重新指向头结点
            // 如果插入位置为0则直接返回原列表
            if (k % length == 0)
                return head;
            // 找到插入位置
            int insetLocation = length - (k % length);
            for (int i = 1; i < insetLocation; i++) {
                pre = pre.next;
            }
            // 调整链表
            ListNode newHead = pre.next;
            pre.next = null;
            last.next = head;
            return newHead;
        }

    }
}

public class Solution061 {

}
